#include <bits/stdc++.h>

using namespace std;

// 展示填函数风格的测试方式
// 子矩阵的最大累加和问题，不要求会解题思路，后面的课会讲
// 测试链接 : https://www.nowcoder.com/practice/840eee05dccd4ffd8f9433ce8085946b

class SubMatrix 
{
public:
    int sumOfSubMatrix(vector<vector<int>> mat, int n) 
    {
        return maxSumSubmatrix(mat, n, n);
    }

    // 求子矩阵的最大累加和，后面的课会讲
    int maxSumSubmatrix(vector<vector<int>>& mat, int n, int m)
    {
        int mx = INT_MIN;
        // 将矩阵压缩成数组
        for(int i = 0; i < n; ++i)
        {
            // 需要的辅助数组，临时动态生成就可以
            int arr[m];
            // i ~ j 行的矩阵压缩成 arr 数组
            memset(arr, 0, sizeof arr);
            for(int j = i; j < n; ++j)
            {
                for(int k = 0; k < m; ++k)
                {
                    arr[k] += mat[j][k];
                }
                mx = max(mx, maxSumSubarray(arr, m));
            }
        }
        return mx;
    }

    // 求子数组的最大累加和，后面的课会讲
    int maxSumSubarray(int* arr, int m)
    {
        int mx = INT_MIN;
        int cur = 0;
        for(int i = 0; i < m; ++i)
        {
            cur += arr[i];
            mx = max(mx, cur);
            cur = cur < 0 ? 0 : cur;
        }
        return mx;
    }
};